/*
 * @Author: szx
 * @Date: 2022-05-23 14:47:13
 * @LastEditTime: 2022-05-23 14:51:44
 * @Description:
 * @FilePath: \leetcode\面试题\08\08\08.js
 */
/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function (S) {
    S = Array.from(S).sort();
    const n = S.length;
    const used = new Array(n).fill(false);
    const res = [];
    const backtrace = (path) => {
        if (path.length == n) {
            res.push(path.join(''));
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i] || (i > 0 && S[i - 1] === S[i] && !used[i - 1])) continue;
            used[i] = true;
            path.push(S[i]);
            backtrace(path);
            path.pop();
            used[i] = false;
        }
    };
    backtrace([], 0);
    return res;
};
